/*
 * @lc app=leetcode.cn id=43 lang=golang
 *
 * [43] 字符串相乘
 */

// @lc code=start
package main

import (
	"sort"
	"strings"
)

// func main() {
// 	print(multiply("2", "3"))
// }

func multiply(num1 string, num2 string) string {
	nums := []string{num1, num2}
	sort.Strings(nums)
	res := make([]string, 0)
	// if len(num1) < len(num2) {
	// 	num1, num2 = num2, num1
	// }
	num1, num2 = nums[1], nums[0]
	n := len(num2)
	for i := 0; i < n; i++ {
		tmp := "0"
		t := num2[i]
		for j := 0; j < int(t-'0'); j++ {
			// fmt.Println(tmp, num1)
			tmp = add(tmp, num1)
		}
		res = append(res, tmp)
	}
	if len(res) == 0 {
		return ""
	}
	// fmt.Println(res)
	tmp := res[0]
	for i := 1; i < len(res); i++ {
		tmp = add(tmp+"0", res[i])
	}
	return tmp
}

// str 相加
func add(s1, s2 string) string {
	m, n := len(s1), len(s2)
	tmp := 0
	res := make([]byte, 0)
	i, j := m-1, n-1
	for ; i >= 0 && j >= 0; i, j = i-1, j-1 {
		b, t := bAdd(s1[i], s2[j], tmp)
		tmp = t
		res = append(res, b)
	}
	for i >= 0 {
		b, t := bAdd(s1[i], '0', tmp)
		tmp = t
		res = append(res, b)
		i--
	}
	// fmt.Println("---", res, i, j)
	for j >= 0 {
		b, t := bAdd(s2[j], '0', tmp)
		tmp = t
		res = append(res, b)
		j--
	}
	if tmp != 0 {
		res = append(res, '0'+uint8(tmp))
	}
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	var s strings.Builder
	s.Write(res)
	return s.String()
}

// 一位byte相加
func bAdd(b1, b2 byte, tmp int) (byte, int) {
	b := int(b1-'0') + int(b2-'0') + tmp
	return uint8(b%10) + '0', b / 10
}

// @lc code=end
